package arithmetic;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 *  算法描述：给定一个数组，里面有一组数字，给定一个target，在数组中找出两个数和等于target的两个索引
 */
public class ToSum {

    public static void main(String[] args) {
        ToSum  toSum=new ToSum();
        int[] numbers={1,4,3,7,5,4,11,22,42,6,0,7,8,9,13};
        int target=22;
        int []  targetIndex= toSum.twoSum(numbers,target);
        System.out.println(Arrays.toString(targetIndex));
    }

    /**
     *  算法一：双重for循环  效率低  时间复杂度是  O(n^2)
     * @param numbsers   给定的元数组
     * @param target  给定的目标数字
     * @return  返回求和的索引数组
     */
    private int[] getTargetIndex(int[] numbsers, int target) {
      for(int i=0;i<numbsers.length;i++){
          for(int j=i+1;j<numbsers.length;j++){
              int k=numbsers[j]+numbsers[i];
              if(k==target){
                  return new int[]{i,j};
              }
          }
      }
      return new int[]{};
    }

    /**
     *  算法2使用Map缓存下数组的值和索引，值作为键，索引作为值，每次取出一个数组的值后，就存到map中，并且利用 target-nums[i]来确定另一个值，
     *  将另一个值利用map的containKey()  方法判断另一个值是否在缓存中，如果在，那么当前i和map.get(target-nums[i])就是两个数之和等于目标数的索引。
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("No two sum solution");
    }



}
